3535. Вася и матрица

Васе мама подарила прямоугольную матрицу n на m. В каждой ячейке матрицы записано целое число. Вася долго игрался в разные математические игры с ней: то быстро вычислял её детерминант, то с легкость возводил её в разные степени.

Но такие игры ему немного надоели, поэтому он придумал себе новое развлечение: он выбирает целое число k и пробует найти подматрицу максимальной площади, в которой сумма всех чисел не превышает k. Подматрица – это прямоугольный участок матрицы.

Вход. В первой строке заданы три целых числа n, m и k (1 ≤ n, m ≤ 300, 1 ≤ k ≤ 10⁹).

В последующих n строках задано по m неотрицательных целых чисел, каждое из которых не превышает 1000.

Выход. Выведите площадь максимальной подматрицы, сумма чисел в которой не превышает k.

Пример входа	Пример выхода
3 3 12 7 5 7 8 4 8 4 3 2	3

РЕШЕНИЕ

динамическое программирование + бинарный поиск

Анализ алгоритма

Пусть a – входная прямоугольная матрица. Создадим двумерный массив dp такого же размера, где dp[i][j] равно сумме чисел на подматрице с противоположными вершинами (1, 1) и (i, j). Его ячейки можно пересчитать по формуле:

dp[i][j] = dp[i – 1][j] + dp[i][j – 1] – dp[i – 1][j – 1] + a[i][j]

Рассмотрим подматрицу массива a размера w * h. Пусть ее противоположные вершины имеют координаты (i, j) и (i + w – 1, j + h – 1).

Тогда сумма всех чисел в подматрице равна

dp[i + w – 1][j + h – 1] – dp[i + w – 1][j – 1] – dp[i – 1][j + h – 1] + dp[i – 1][j – 1]

Задачу решаем перебором. Переберем все возможные размеры подматрицы w * h и все возможные левые верхние углы (i, j) расположения этой матрицы. За константное время с помощью массива dp найдем сумму чисел на этой подматрице. Если она не превышает k, то среди всех таких подматриц считаем максимум их площадей. Однако такой перебор за O(n⁴) можно ускорить до O(n³logn) при помощи бинарного поиска по ширине h перебираемой подматрицы.

Зафиксируем левый верхний угол (i, j). Пусть g(w, h) – сумма чисел в подматрице (i, j) – (i + w – 1, j + h – 1). Если зафиксировать w, а h рассматривать как переменную, то g(w, h) является неубывающей функцией относительно h (массив а содержит целые неотрицательные числа). Бинарным поиском находим максимальное h, для которого g(w, h) ≤ k.

Пример

Например, сумма чисел подматрицы (2, 2) – (3, 3) равна 48 – 19 – 19 + 7 = 17.

Реализация алгоритма

Входную матрицу храним в массиве а.

#define MAX 210

int a[MAX][MAX], dp[MAX][MAX];

Функция f(w, h) возвращает 1, если существует такая подматрица размера w * h, что сумма ее элементов не больше k. Перебираются все возможные верхние левые углы (i, j) и с помощью массива dp за константное время определяется сумма чисел в прямоугольнике (i, j) – (i + w – 1, j + h – 1).

int f(int w, int h)

{

int i, j;

for (i = 1; i + w - 1 <= n; i ++)

for (j = 1; j + h - 1 <= m; j ++)

if (dp[i + w - 1][j + h - 1] - dp[i + w - 1][j - 1] –

dp[i - 1][j + h - 1] + dp[i - 1][j - 1] <= k) return 1;

return 0;

};

Основная часть программы. Читаем входную матрицу.

scanf("%d %d %d",&n,&m,&k);

for(i = 1; i <= n; i++)

for(j = 1; j <= m; j++)

scanf("%d",&a[i][j]);

Из входной матрицы а посчитаем матрицу dp.

for (i = 1; i <= n; i++)

for (j = 1; j <= m; j++)

dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];

Перебираем ширину подматрицы w.

answer = 0;

for (w = 1; w <= n; w++)

{

Длину подматрицы перебираем бинарным поиском на интервале [l; r].

l = 1; r = m;

while (l < r)

{

mid = (l + r) / 2;

Для подматрицы размера w * mid рассматриваем все возможные левые верхние позиции (i, j). Если существует такое ее положение, что сумма чисел в ней не больше k, то пересчитываем результирующую площадь answer.

if (f(w,mid))

{

answer = max(answer, w * mid);

l = mid + 1;

}

else r = mid;

}

mid = (l + r) / 2;

if (f(w,mid))

answer = max(answer, w * mid);

};

Выводим площадь искомой максимальной подматрицы.

printf("%d\n",answer);